package com.wc.data_structures.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author congge
 * @Date 2023/4/24 21:56
 * @description 顺序存储二叉树
 */
public class ArrayBinaryTree<T> {
    private T[] array;

    public ArrayBinaryTree() {

    }

    public ArrayBinaryTree(T[] array) {
        this.array = array;
    }

    public static void main(String[] args) {
        Integer[] array = {1, 2, 3, 4, 5, 6};
        ArrayBinaryTree<Integer> arrayBinaryTree = new ArrayBinaryTree(array);
        List<Integer> preOrderList = arrayBinaryTree.preOrder();
        for (int num : preOrderList) {
            System.out.print(num + " ");
        }
    }

    /**
     * 顺序存储的前序遍历
     *
     * @return
     */
    public List<T> preOrder() {
        List<T> preOrderList = new ArrayList<>();
        preOrder(0, preOrderList);
        return preOrderList;
    }

    /**
     * @param index        数组下标
     * @param preOrderList 存储前序遍历的数据
     */
    public void preOrder(int index, List<T> preOrderList) {
        // 如果数组为空 或是 arr.length = 0
        if (index < 0 || index > array.length - 1) {
            return;
        }
        preOrderList.add(array[index]);
        // 左面递归遍历
        preOrder(index * 2 + 1, preOrderList);
        // 右面递归遍历
        preOrder(index * 2 + 2, preOrderList);
    }

    /**
     * 中序遍历
     *
     * @return 遍历后的数组
     */
    public List<T> inOrder() {
        List<T> inOrderList = new ArrayList<>();
        inOrder(0, inOrderList);
        return inOrderList;
    }

    /**
     * 中序遍历
     *
     * @param index       数组下标
     * @param inOrderList 存储前序遍历的数据
     */
    public void inOrder(int index, List<T> inOrderList) {
        // 如果数组为空 或是 arr.length = 0
        if (index < 0 || index > array.length - 1) {
            return;
        }

        // 左面递归遍历
        preOrder(index * 2 + 1, inOrderList);
        inOrderList.add(array[index]);
        // 右面递归遍历
        preOrder(index * 2 + 2, inOrderList);
    }

    /**
     * 后序遍历
     *
     * @return 遍历后的数组
     */
    public List<T> postOrder() {
        List<T> postOrderList = new ArrayList<>();
        inOrder(0, postOrderList);
        return postOrderList;
    }

    /**
     * 后序遍历
     *
     * @param index         数组下标
     * @param postOrderList 存储前序遍历的数据
     */
    public void postOrder(int index, List<T> postOrderList) {
        // 如果数组为空 或是 arr.length = 0
        if (index < 0 || index > array.length - 1) {
            return;
        }

        // 左面递归遍历
        preOrder(index * 2 + 1, postOrderList);
        // 右面递归遍历
        preOrder(index * 2 + 2, postOrderList);
        postOrderList.add(array[index]);
    }
}
